package ru.osu.acm.testing.solutions;

import java.io.*;
import java.util.StringTokenizer;
import java.util.Random;

/**
 * User: Aleksey
 * Date: 04.03.2009
 * Time: 10:15:43
 */
public class Task9 implements Runnable {
    private static BufferedReader br = null;
    private static PrintWriter pw = null;
    private static StringTokenizer st = new StringTokenizer("");

    private void nline() {
        try {
            st = new StringTokenizer(br.readLine());
        }
        catch (IOException e) {
            throw new RuntimeException("RuntimeException");
        }
    }

    private int ni() {
        while (!st.hasMoreTokens()) nline();
        return Integer.parseInt(st.nextToken());
    }

    private long nl() {
        while (!st.hasMoreTokens()) nline();
        return Long.parseLong(st.nextToken());
    }

    private double nd() {
        while (!st.hasMoreTokens()) nline();
        return Double.parseDouble(st.nextToken());
    }

    private String ns() {
        while (!st.hasMoreTokens()) nline();
        return st.nextToken();
    }

    private void soutCurD(int[] d, int n) {
        String x = "";
        for (int i = 0; i < n; i++) {
            x += d[i] + (i == n-1 ? "" : " ");
        }
        pw.println(x);
    }

    private void solve() {
        int n = ni();
        int[][] m = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                m[i][j] = ni();
            }
        }
        int[] d = new int[n];
        boolean[] used = new boolean[n];

        d[0] = 0;
        used[0] = true;
        for (int i = 1; i < n; i++) {
            int best = -1;
            for (int j = 0; j < n; j++) {
                if (!used[j] && (best == -1 || m[d[i-1]][j] < m[d[i-1]][best])) {
                    best = j;
                }
            }
            d[i] = best;
            used[best] = true;
        }
        soutCurD(d, n);

        while (true) {
            boolean ok = false;

            for (int i = 1; i < n; i++) {
                for (int j = i+1; j < n; j++) {
                    if (j-i > 1) {
                        int dBefore = m[d[i-1]][d[i]] + m[d[i]][d[i == n-1 ? 0 : i+1]] + m[d[j-1]][d[j]] + m[d[j]][d[j == n-1 ? 0 : j+1]];
                        int dAfter = m[d[i-1]][d[j]] + m[d[j]][d[i == n-1 ? 0 : i+1]] + m[d[j-1]][d[i]] + m[d[i]][d[j == n-1 ? 0 : j+1]];
                        if (dAfter < dBefore) {
                            ok = true;
                            int work = d[i];
                            d[i] = d[j];
                            d[j] = work;
                            pw.println(i + " " + j);
                        }
                    }
                    else {
                        int dBefore = m[d[i-1]][d[i]] + m[d[i]][d[j]] + m[d[j]][d[j == n-1 ? 0 : j+1]];
                        int dAfter = m[d[i-1]][d[j]] + m[d[j]][d[i]] + m[d[i]][d[j == n-1 ? 0 : j+1]];
                        if (dAfter < dBefore) {
                            ok = true;
                            int work = d[i];
                            d[i] = d[j];
                            d[j] = work;
                            pw.println(i + " " + j);
                        }
                    }
                }
            }

            if (!ok) {
                break;
            }
        }
        pw.println("optimal");
    }

    public void run() {
        solve();
        pw.close();
    }

    private static void generate(int k, int minn, int maxn) {
        try {
            PrintWriter pw = new PrintWriter("input" + k + ".txt");

            Random rand = new Random();
            int n = rand.nextInt(maxn - minn) + minn;
            pw.println(n);
            int[][] m = new int[n][n];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == j) {
                        m[i][j] = 0;
                    }
                    else if (i < j) {
                        m[i][j] = rand.nextInt(100) + 1;
                    }
                    else {
                        m[i][j] = m[j][i];
                    }

                    pw.print(m[i][j] + (j == n-1 ? "\n" : " "));
                }
            }

            pw.close();
        }
        catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        /*br = new BufferedReader(new InputStreamReader(System.in));
        pw = new PrintWriter(new OutputStreamWriter(System.out));*/

        try {
            br = new BufferedReader(new FileReader("salesmanopt.in"));
            pw = new PrintWriter("salesmanopt.out");
        }
        catch (FileNotFoundException e) {
            throw new RuntimeException("RuntimeException");
        }

        new Thread(new Task9()).start();

        /*for (int i = 0; i < 2; i++) {
            generate(i, 3, 5);
        }
        for (int i = 2; i < 5; i++) {
            generate(i, 5, 15);
        }
        for (int i = 5; i < 10; i++) {
            generate(i, 20, 100);
        }
        for (int i = 10; i < 12; i++) {
            generate(i, 100, 200);
        }*/
    }
}
